\input{euler.tex}

\begin{document}

\problem[318]{2011 Nines}

Consider the real number $\sqrt{2} + \sqrt{3}$. When we calculate the even powers of $\sqrt{2} + \sqrt{3}$, we get:
\begin{align}
 (\sqrt{2} + \sqrt{3})^2 &= 9.898979485566356... \notag \\
 (\sqrt{2} + \sqrt{3})^4 &= 97.98979485566356... \notag \\
 (\sqrt{2} + \sqrt{3})^6 &= 969.998969071069263... \notag \\
 (\sqrt{2} + \sqrt{3})^8 &= 9601.99989585502907... \notag \\
 (\sqrt{2} + \sqrt{3})^{10} &= 95049.999989479221... \notag \\
 (\sqrt{2} + \sqrt{3})^{12} &= 940897.9999989371855... \notag \\
 (\sqrt{2} + \sqrt{3})^{14} &= 9313929.99999989263... \notag \\
 (\sqrt{2} + \sqrt{3})^{16} &= 92198401.99999998915... \notag
\end{align}

It looks like that the number of consecutive nines at the beginning of the fractional part of these powers is non-decreasing. In fact it can be proven that the fractional part of $(\sqrt{2}+\sqrt{3})^{2n}$ approaches 1 for large $n$.
 
Consider all real numbers of the form $\sqrt{p}+\sqrt{q}$ where $p, q$ are positive integers and $p < q$, such that the fractional part of $(\sqrt{p}+\sqrt{q})^{2n}$ approaches 1 for large $n$.
 
Let $C(p,q,n)$ be the number of consecutive nines at the beginning of the fractional part of $(\sqrt{p}+\sqrt{q})^{2n}$. 

Let $N(p,q)$ be the minimal value of $n$ such that $C(p,q,n) \ge 2011$. 

Find $\sum N(p,q)$ for $p+q \le 2011$. 

\solution

Let $A_n = (\sqrt{q}+\sqrt{p})^{2n}$ and $B_n = (\sqrt{q}-\sqrt{p})^{2n}$. We claim that $(A_n + B_n)$ is an integer, because
\begin{align}
A_n + B_n &= (\sqrt{q}+\sqrt{p})^{2n} + (\sqrt{q}-\sqrt{p})^{2n} \notag \\
&= \sum_{i=0}^{2n} \binom{2n}{i} (\sqrt{q})^i (\sqrt{p})^{2n-i} 
 + \sum_{i=0}^{2n} \binom{2n}{i} (\sqrt{q})^i (-\sqrt{p})^{2n-i} \notag \\
&= \sum_{k=0}^n \binom{2n}{2k} q^k p^{n-k} . \notag
\end{align}
Therefore, if and only if $B_n$ approaches 0 for large $n$, $A_n$ will have a fractional part with increasingly many leading nines. This is equivalent to the condition $| \sqrt{q} - \sqrt{p} | < 1$.

For a pair of qualified $(p,q)$, in order for $A_n$ to have at least $m$ leading nines in its fractional part, we must have $B_n = B_0^{2n} \le 10^{-m}$. This leads to $n \ge - m/(2 \log_{10} B_0)$. Hence
\[
N(p,q) = \left\lceil -\frac{m}{2 \log_{10} B_0} \right\rceil .
\]

For this problem, we just enumerate all qualified $(p,q)$, and sum up $N(p,q)$ to get the answer.

\answer

709313889

\complexity

Let $N$ be the upper bound of $p+q$ (2011 in this problem). Then we have:

Time complexity: $\BigO(N^2)$

Space complexity: $\BigO(1)$

\end{document} 